package club.xiaojiawei.binarytree;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/16/22 11:34 PM
 * @question 105. 从前序与中序遍历序列构造二叉树
 * @description 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
 */
public class BuildTree105 {

    public static void main(String[] args) {
        TreeNode result = buildTree2(new int[]{1, 2}, new int[]{2, 1});
        System.out.println(result);
    }

    /**
     * 官方-迭代(没理解透彻)
     * @param preorder
     * @param inorder
     * @return
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        stack.push(root);
        int inorderIndex = 0;
        for (int i = 1; i < preorder.length; i++) {
            int preorderVal = preorder[i];
            TreeNode node = stack.peek();
            if (node.val != inorder[inorderIndex]) {
                node.left = new TreeNode(preorderVal);
                stack.push(node.left);
            } else {
                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
                    node = stack.pop();
                    inorderIndex++;
                }
                node.right = new TreeNode(preorderVal);
                stack.push(node.right);
            }
        }
        return root;
    }

    static int[] preorder;

    static HashMap<Integer, Integer> map;

    static int index = -1;

    /**
     * 递归
     * @param preorder
     * @param inorder
     * @return
     */
    public static TreeNode buildTree2(int[] preorder, int[] inorder) {
        if (preorder.length == 1){
            return new TreeNode(preorder[0]);
        }
        BuildTree105.preorder = preorder;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        BuildTree105.map = map;
        return recursion(0, inorder.length - 1);
    }

    public static TreeNode recursion(int left, int right){
        if (left > right){
            return null;
        }
        BuildTree105.index++;
        TreeNode node = new TreeNode(preorder[BuildTree105.index]);
        Integer index = map.get(preorder[BuildTree105.index]);
        node.left = recursion(left, index - 1);
        node.right = recursion(index + 1, right);
        return node;
    }

    /**
     * 民间-递归(nb)
     * @param preorder
     * @param inorder
     * @return
     */
    public TreeNode buildTree3(int[] preorder, int[] inorder) {
        return buildTree(preorder, inorder, Integer.MIN_VALUE);
    }

    private int in = 0;

    private int pre = 0;

    public TreeNode buildTree(int[] preorder,int[] inorder,int stop){
        if(pre >= preorder.length){
            return null;
        }
        if(inorder[in] == stop){
            in++;
            return null;
        }
        TreeNode root = new TreeNode(preorder[pre++]);
        root.left = buildTree(preorder, inorder, root.val);
        root.right = buildTree(preorder, inorder, stop);
        return root;
    }

    static class TreeNode{

        private int val;

        private TreeNode left;

        private TreeNode right;

        public TreeNode() {
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        public TreeNode(int val) {
            this.val = val;
        }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public TreeNode getLeft() {
            return left;
        }

        public void setLeft(TreeNode left) {
            this.left = left;
        }

        public TreeNode getRight() {
            return right;
        }

        public void setRight(TreeNode right) {
            this.right = right;
        }
    }
}
